HDU1705 皮克定理

Posted on | In , ,

给定一个三角形三点坐标，问三角形内有多少个坐标均为整数的点。

皮克定理

给定顶点座标均是整点（或正方形格子点）的简单多边形，皮克定理说明了其面积 ${\displaystyle S}$ 和内部格点数目 ${\displaystyle i}$ 、边上格点数目 ${\displaystyle b}$ 的关系
$$
S=i+ \frac{b}{2}-1
$$

分析

边上格点数通过gcd算出，直接套用公式即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;

int x1, x2, x3, y1, y2, y3;

int gcd(int a, int b)
{
    return b==0 ? a : gcd(b, a%b);
}

int main()
{
    while(scanf("%d%d%d%d%d%d", &x1, &y1, &x2, &y2, &x3, &y3)!=EOF)
    {
        if(x1==0 && y1==0 && x2==0 && y2==0 && x3==0 && y3==0) break;
        int s = abs((x2-x1)*(y3-y1)-(x3-x1)*(y2-y1))/2;
        int p=0;
        p += gcd(abs(x1-x2), abs(y1-y2));
        p += gcd(abs(x3-x2), abs(y3-y2));
        p += gcd(abs(x1-x3), abs(y1-y3));
        printf("%d\n", s-p/2+1);
    }
}